package com.datastructure.test.packet01;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class Packet01 {

    ArrayList<Good> data = new ArrayList<>();
    ArrayList<ArrayList<Good>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[][] data = {{1,3},{9,8}};
        Packet01 packet01 = new Packet01();
        int knapsack = packet01.knapsack(10, 2, data);
        System.out.println(knapsack);
    }

    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        Good good = null;
        int sumVolume = 0;
        int max = 0;
        int weightGood = 0;
        for (int i = 0; i < n; i++) {
            good = new Good(vw[i][0],vw[i][1]);
            data.add(good);
        }
        Deque<Good> deque = new ArrayDeque<>();
        generateGoods(0,data,deque);
        for (ArrayList<Good> re : res) {
            weightGood = 0;
            sumVolume=0;
            for (Good good1 : re) {
                sumVolume+= good1.volume;
                weightGood+=good1.weight;
            }
            if(sumVolume<=V){
                max = Math.max(max,weightGood);
            }
        }
        return max;
    }

    private void generateGoods(int start,ArrayList<Good> data, Deque<Good> deque) {
        res.add(new ArrayList<>(deque));
        for(int i = start;i< data.size();i++){
            deque.add(data.get(i));
            generateGoods(i+1,data,deque);
            deque.removeLast();
        }
    }

}

class Good{
    int volume;
    int weight;

    public Good(int volume, int weight) {
        this.volume = volume;
        this.weight = weight;
    }
}
